package mo.leetcode_top;

import java.util.*;

public class L140 {

    private Map<String, List<String>> map = new HashMap<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        if (map.containsKey(s)) {
            return map.get(s);
        }
        List<String> list = new ArrayList<>();
        if (s.length() == 0) {
            list.add("");
            return list;
        }
        for (String str : wordDict) {
            if (s.startsWith(str)) {
                List<String> subList = wordBreak(s.substring(str.length()), wordDict);
                for (String sub : subList) {
                    list.add(str + ("".equals(sub) ? "" : " ") + sub);
                }
            }
        }
        map.put(s, list);
        return list;
    }

    public static void main(String[] args) {
        L140 test = new L140();
        System.out.println(test.wordBreak("catsanddog", Arrays.asList("cat","cats","and","sand","dog")));
    }
}
